The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Border Gateway Protocol (BGP) is a peer-to-peer routing protocol the latest version of which, BGP-4, is defined in RFC1771 that was published by the Internet Engineering Task Force (IETF) in March 1995. BGP is an exterior gateway protocol that is used to exchange routing information among network elements (usually routers) in the same or different autonomous systems. A computer host that executes one or more BGP processes is typically referred to as a BGP host or a BGP device. In order to exchange routing information, two BGP hosts, or peers, first establish a transport protocol connection with one another. The transport connection may be established over a Transport Layer protocol, such as Transmission Control Protocol (TCP) or Stream Control Transmission Protocol (SCTP). Once the transport connection is established, the BGP peers establish a BGP session by exchanging a series of messages that define the parameters of the session.
After the BGP session is established, the BGP peers exchange, or advertise, all their routing information. Thereafter, only updates or changes to the routing information are advertised between the BGP peers. The BGP peers maintain the exchanged routing information during the existence of the BGP session, and when the BGP session is closed or terminated for whatever reason, the routing information received during the session is typically discarded.
The routing information exchanged between BGP peers includes routes to address destinations in one or more networks. A route comprises an address prefix of the destination (also referred to as prefix), and attributes that describe the path to the destination. At a BGP host, routes are stored in a Routing Information Base (RIB). A BGP RIB usually includes three parts: (a) Adj-RIBs-In, which stores routes received from BGP peers or learned from other protocols, (b) Loc-RIB, which stores routes that the BGP host has selected by applying its local policies to the routes stored in Adj-RIBs-In, and (c) Adj-RIBs-Out, which stores routes that the BGP host has selected for advertisement to its BGP peers. The BGP RIB may be implemented as a single physical routing table that includes each of the three parts as separate logical tables, as separate physical routing tables, or as some combination of one or more logical and/or physical routing tables.
The routes that a BGP host stores in Adj-RIBs-In may be received over a BGP session established with a BGP peer, or over any other routing protocol that is configured and is executing on the BGP host. The routes stored in the Loc-RIB of the BGP host are selected from the routes from Adj-RIBs-In by applying one or more route selection and/or route configuration algorithms. The routes selected by the BGP host and stored in the Loc-RIB usually represent the best paths to the routes' respective destinations. Once the best route to a certain destination is selected and stored in the Loc-RIB, the BGP host advertises the route to its BGP peers by placing, or storing, the route in Adj-RIBs-Out. The BGP host may also select some or all of the Loc-RIB routes and store them in a Forwarding Information Base (FIB). The FIB is a physical or logical table that stores routes used to forward packets to the address destinations of the stored routes.
A BGP host may utilize a variety of path selection and/or path configuration algorithms in making its decision whether to select a route that is stored in the Adj-RIBs-In and/or Loc-RIB. The algorithms may be based on a variety of criteria associated with the attributes of a route including, but not limited to, accessibility of the next hop in the path of the route, the weight assigned to the route by the BGP host, the identity of the network element serving as an exit point from the autonomous system for the route, the identity of the network element from which the route was learned (and/or received), the identity and/or location of the network element that is the next hop in the path, the type of routing protocol over which the route was received, the number of hops to the destination of the route, and the network address of the network element that is the next hop in the path.
The path selection and/or path configuration algorithms utilized by a BGP host are usually a part of a routing policy that is configured at the BGP host. A routing policy is a definition of what mechanisms are used for providing access control and flexible routing of network traffic at a network element, such as a router. One or more routing policies are usually defined to configure the network element to inspect and modify the attributes of the routes stored in its routing tables. A routing policy may be configured as specific to one network element, or may be a global autonomous-system-wide routing policy that is configured on all network elements in the network. The definition of the routing policy determines how routes are processed by the network element or elements. For example, at a BGP host, routing protocols such as BGP make routing decisions to advertise, aggregate, discard, distribute, export, hold, import, redistribute, and otherwise modify routes based on one or more parameters of configured routing policies. Thus, a BGP host may apply different routing policies to different sets of routes in the BGP RIB, and may apply different routing policies to the different routing protocols that the BGP host may be executing.
A BGP host, however, always applies its routing policies to the routes that are currently stored in the RIB. This presents a problem since a BGP host has no way of knowing what routes it will receive before a BGP session is established or during the lifetime of the session. In particular, the BGP host does not have the capability to select, configure, and fine-tune a routing policy for routes in the RIB before actually deploying the policy. This often leads to incorrect route selection, propagation of incorrect routes through advertisement, and forwarding packets on incorrect routes. Furthermore, since the BGP host has no way of screening the routes it receives from its peers, it often ends up running path selection and/or path configuration algorithms on routes with unexpected or unwanted prefixes and paths, thus wasting time and valuable processing resources.
One past approach for configuring a routing policy or defining a policy “model” is to initially apply a default routing policy to the routes in the RIB, and consequently tweak the policy by using a trial-and-error technique. For example, once a BGP peering session is established and routes are received over the session, a default policy is applied to these received routes. Usually, a network administrator reviews the received routes and the information obtained as a result of applying the default routing policy to the routes, and makes changes to some or all of the parameters configured for the default routing policy. The changed routing policy is applied again to the routes, the results are reviewed, and the parameters of the policy are modified again. This trial-and-error process continues until an acceptable routing policy is finally configured.
The trial-and-error approach for routing policy configuration has some serious disadvantages. One serious disadvantage of this approach is that it fails to prevent incorrect route selection, incorrect route advertisement, and forwarding packets on incorrect routes while the policy configuration process is taking place at a BGP host. Another serious disadvantage is that this approach may take a long time to configure an acceptable routing policy, and thus may adversely affect the performance of the BGP host with respect to traffic forwarding and route advertisement.
Based on the foregoing, there is a clear need for a technique that overcomes the disadvantages and problems described above, and that allows for flexible route screening, for BGP session interaction, and for robust routing policy modeling and configuration.